package leetcode; /**
 * description:
 * author:张腾
 * date:2021-06-26
 */

import java.util.Arrays;
import java.util.HashMap;

/**
 * 和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
 *
 * 现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。
 *
 * 数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
 */

public class leetcode594 {
//    public int findLHS(int[] nums) {
//        HashMap<Integer, Integer> map = new HashMap<>();
//        int res = 0;
//        for (int num : nums) {
//            map.put(num,map.getOrDefault(num,0)+1);
//            if (map.containsKey(num-1)) res = Math.max(res,map.get(num-1)+map.get(num));
//            if (map.containsKey(num+1)) res = Math.max(res,map.get(num+1)+map.get(num));
//        }
//        return res;
//    }

    public int findLHS(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, ans = 0;
        for (int i = 0,j = 0; j < n; j++) {
            while (i < j && nums[j] - nums[i] > 1) i++;
            if (nums[j] - nums[i] == 1) ans = Math.max(ans,j - i + 1);
        }
        return ans;
    }
}
